package SortMethod;

import SortHelper.SortHelper;

import java.util.Random;

//这次是写才是我理想中的快排，从两边同时开始遍历
public class QuickSort02 {

    private QuickSort02(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        Random rnd = new Random(); //下面函数设置一个接口，就不用每次调用都新建一个对象，而是直接使用
        sort(arr,0,arr.length - 1,rnd);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random rnd){
        if (l >= r) return;
        int p = partition(arr,l,r,rnd);
        sort(arr,l,p - 1,rnd); //p - 1才是左半边，只写个p会报错，头一次意识到
        sort(arr,p + 1,r,rnd);
    }

    private static <E extends Comparable<E>> int partition(E[] arr,int l,int r,Random rnd){
        int p = l + rnd.nextInt(r - l + 1);
        SortHelper.swap(arr,l,p);
        int i = l + 1,j = r;
        //思路就是，还是设置第一个数为标志，从第二个和最后一个数开始遍历
        //循环开始，第一个循环找到比标志还要大的数，第二个循环结束找到比标志还要小的数
        //如果i>=j,说明数组已经按要求完成，直接退出。
        //如果没完成，就说明第一个循环和第二个循环都已经找到了，直接进行交换
        //交换完成记得维护i，j让他们下一轮循环要从正确位置开始找
        //最后记得l和j换一下位置，因为此时的j是比i小的（临界i++,j--导致），只能和j换位置
        while(true){
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i++;
            while (j >= i && arr[j].compareTo(arr[l]) > 0)
                j--;
            if (i >= j) break; //记得一定要设置出口，不然while true不会退出去
            SortHelper.swap(arr,i,j);
            i++;
            j--;
        }
        SortHelper.swap(arr,l,j);
        return j;
    }

    //自己测试的主函数
//    public static void main(String[] args) {
//        Random rnd = new Random();
//        Integer[] arr = {7,5,2,5,1,2};
//        int p = partition(arr,0,arr.length-1,rnd);
//        System.out.println(p);
//        sort(arr,0,arr.length - 1,rnd);
//        for (int n : arr){
//            System.out.printf("%d ",n);
//        }
//    }
}
